//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 
//
// 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/ 
//
// Related Topics 递归 链表 👍 506 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 方法一：双指针迭代修改next指向
     * 让当前结点指向头结点，当前结点的前一个节点初始为空
     * 当前结点不等于null时，循环遍历链表
     * 循环中改变next指针的指向
     * 注意：在修改next指针指向时，先要临时保存当前的下一个结点，防止链表丢失
     */
    /*public ListNode reverseList(ListNode head) {

        ListNode cur = head, pre = null;

        while(cur != null) {
            ListNode tmp = cur.next; // 临时存放cur.next
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }*/


    /**
     * 方法二：利用递归回溯修改next指向
     * 递归终止条件：当前结点为空返回
     * 递归：一直递归到最后一个不为null的节点，然后开始回溯修改next指向
     */
     public ListNode reverseList(ListNode head) {
         return recur(head, null);
     }

     private ListNode recur(ListNode cur, ListNode pre) {

         if (cur == null) return pre;

         ListNode res = recur(cur.next, cur); //递归调用
         cur.next = pre;  // 修改节点引用指向
         return res;
     }

}
//leetcode submit region end(Prohibit modification and deletion)
